I. Field of the Invention
This invention relates generally to communication systems. More specifically, the invention relates to random access communication systems.
II. Description of the Related Art
The use of wireless communication systems for the transmission of digital data is becoming more and more pervasive. In a wireless system, the most precious resource in terms of cost and availability is typically the wireless link itself. Therefore, one major design goal in designing a communication system comprising a wireless link is to efficiently use the available capacity of the wireless link. In addition, it is also important to minimize the delay associated with data transmissions.
In a system in which multiple units compete for finite system resources, a means must be developed to regulate access to such resources. In a digital system, remote units tend to generate bursty data. The bursty data is characterized in that it has a high peak-to-average traffic ratio, meaning that large blocks of data are transferred during short periods of time interposed between significantly longer periods of idleness. Dedication of an individual communication channel to each active unit does not result in efficient use of system capacity in a system in which units generate bursty data because, during those times when the remote unit is not utilizing the system, the allocated channel remains idle. The use of dedicated channels also may impose a hard limit on the number of remote units which may simultaneously use the system regardless of the usage patterns of the remote units. In addition, the use of dedicated channels may cause unacceptable delay if the slice of capacity allocated to each remote unit is so small that data transfer rates are greatly compromised.
The characteristics of the inbound and outbound traffic tend to differ significantly in a digital data system. For example, in a system which provides wireless Internet services, a typical inbound transmission from a remote unit is relatively short, such as a request for a web page. However, a typical outbound data transfer to a remote unit tends to be rather large. For example, in response to a request for a web page, the system may transfer a significant amount of data. Because the characteristics of the inbound and outbound channel are very different, system efficiency may be increased by developing two distinct protocols for the inbound and outbound links.
A random access ALOHA protocol was developed for use in the inbound link from a remote unit in a digital data system. The basic idea behind ALOHA is quite simple: the remote units transmit whenever they have data to send. If the remote units are using a communication resource which can only be accessed by one remote unit at a time, the information from each remote unit is destroyed if two units transmit at the same time causing a collision. In a system where the remote unit can monitor the random access channel, the remote unit may listen to the channel in order to determine whether its transmission is the victim of a collision. In a system in which the remote unit does not or cannot monitor the random access channel, the remote unit may detect a collision based upon the absence of an acknowledgment received from a hub station in response to a transmission. According to standard ALOHA operation, whenever a collision occurs, the remote unit waits a random amount of time and retransmits the data. The waiting time must be random or the colliding remote units generate collisions in lockstep over and over again.
FIG. 1 is a timing diagram showing the operation of a pure ALOHA random multiple access system. As shown in shown in FIG. 1, five remote units designated A, B, C, D and E are transmitting packets of data within a common communication channel. Whenever two remote units transmit at the same time, a collision occurs and both transmissions are lost. In a pure ALOHA system, if the first bit of a new transmission overlaps just the last bit of a transmission already in progress, both transmissions are totally destroyed and both have to be retransmitted at some other time. For example, in the frequency modulated (FM) channel shown in FIG. 1 where no two packets may contemporaneously be transmitted, a packet 12 transmitted by remote unit B collides with a packet 10 transmitted by the remote unit A and a packet 14 transmitted by remote unit C. The remote unit A must retransmit the information in the packet 10, the remote unit B must retransmit the information in the packet 12 and the remote unit C must retransmit the information in the packet 14. FIG. 1 shows the remote unit C retransmitting the packet 14 as packet 14R.
In a pure ALOHA system, if the average packet transfer rate is low, most packets are transferred without a collision. As the average packet transfer rate begins to increase, the number of collisions increases and, hence, the number of retransmissions also increases. As the average packet transfer rate increases linearly, the probability of retransmissions and multiple retransmissions increases exponentially. As some point as the average packet transfer rate increases, the probability of successful transmission falls below a reasonable number and the system becomes practically inoperable. In a pure ALOHA system, the best channel utilization which can be achieved is approximately 18%. Below 18%, the system is underutilized. Above 18%, the number of collisions increases such that the throughput of the system begins to fall.
The introduction of a satellite link within a digital communication system complicates the multiple access dilemma. The use of a geosynchronous satellite typically introduces a 270 millisecond (msec) delay between transmission of a signal from a remote unit and reception of that same signal at a hub station. Due to the delay introduced by a satellite link, scheduled access schemes which require the remote unit to request system resources before beginning any transmission are impractical for many applications. Therefore, a satellite link which serves a great number of remote units which transmit bursty data is a likely environment in which to implement an ALOHA system.
If an ALOHA system is implemented in a satellite system in which the remote units can""t or don""t monitor the random access channel, in the event of a collision, the remote unit does not know of the collision for at least 540 msec. In addition to the notification delay, the remote unit typically must wait some random amount of time before retransmitting the data (to avoid lockstep retransmissions). The retransmitted signal is once again subjected to the 270 msec time delay. The cumulative delay of such a transmission can easily exceed one second. In a fully loaded system, the delay can be significantly longer due to the increased probability of repeated collisions. Therefore, when using a satellite link, it is advantageous to limit the number of retransmissions attributable to collisions as well as other causes. The number of retransmissions due to collisions can be decreased by simply reducing the allowable system load.
The satellite link also introduces challenges concerning the successful transmission of data over the link. Due to the high level of interference and high path loss which characterizes a satellite link, typically a relatively robust physical interface must be used. One physical interface commonly used over satellite links is direct sequence spread spectrum (DSSS). In a prior art DSSS system, the communication channel is defined by a maximal length binary spreading sequence. Each discrete binary value which makes up a spreading sequence is referred to as a xe2x80x9cchip.xe2x80x9d The spreading sequence is selected such that the autocorrelation of the sequence with itself is nearly zero for all chip-aligned offsets other than zero. A maximal length pseudo noise (PN) sequence of length n has the property that its circular correlation with itself (autocorrelation) is either 1 or 1/n for any chip-aligned offset. The correlation of the chosen spreading sequence with itself is equal to 1/n for all chip-aligned offsets other than the zero offset. The correlation is also 1/n between the sequence and its inversion for any chip-aligned offset other than the zero offset. The correlation of the sequence and itself at zero time offset is equal to 1. Thus, as the spreading sequence length n increases, the orthogonality and, hence, isolation between the corresponding channels also increases. The means by which maximal length sequences can be identified and generated are well-known in the art.
In a typical system, each data bit generated by the remote unit is modulated with one or more chips before transmission over the wireless link. In this way, the narrow band digital data is spread across a wider transmission bandwidth. At the receiver, the received data is multiplied by the same spreading sequence which was used to create the signal in order to extract the corresponding digital data. Because the DSSS signal waveform is robust in the presence of interference, the number of retransmissions due to interference other than collisions may be decreased by incorporation of the DSSS signaling.
In a DSSS system, the remote units transmit in a common frequency band, thereby causing some level of interference to other system users. System efficiency in a DSSS system is increased if the power received at the hub station from each remote unit is controlled such that each signal arrives at the hub station receiver at approximately the same level. If a signal transmitted by a remote unit arrives at the hub station receiver at a power level that is relatively low, the signal quality may fall below an acceptable level. If, on the other hand, the remote unit signal arrives at a power level that is relatively high, the high power signal acts as unnecessary interference to other remote units. Typically, the power transmitted by the remote units is controlled by the hub station. The hub station sends power adjustment commands to the remote unit in order to equalize the power received at the hub station.
FIG. 2 is a timing diagram illustrating prior art spread spectrum ALOHA random access operation for five exemplary remote units Axe2x80x2, Bxe2x80x2, Cxe2x80x2, Dxe2x80x2 and Exe2x80x2 using an identical code. For purposes of illustration, the system in FIG. 2 uses a spreading code which is only seven chips (c1-c7) in length. In actual systems, the length of the spreading code is likely to be longer such as 255 chips in length. At time slot t1 the remote unit Axe2x80x2 begins to transmit a series of data bits each modulated with the entire seven bit spreading sequence. In systems using longer spreading sequences, it is likely that each data bit is spread with only a subset of the entire spreading sequence. At time t3, the remote unit Exe2x80x2 begins to transmit a series of data bits modulated by the same seven chip spreading code. Likewise at time t5, the remote unit Cxe2x80x2 begins to transmit a series of a data bits modulated by the same seven chip spreading code.
As noted above, the spreading sequence is selected such that it is nearly orthogonal with itself at all chip-aligned offsets other than the zero offset. Therefore, under the scenario depicted by FIG. 2, the remote units Axe2x80x2, Cxe2x80x2 and Exe2x80x2 produce a low level of interference with one another because their respective transmissions are offset from one another. However, should two remote units begin to transmit during this same time slot (resulting in a zero offset), a collision occurs and both transmissions are lost. Because each remote unit spreads its signal with the same spreading sequence, if a collision occurs, each remote unit waits a random amount of time before beginning to transmit again in order avoid repeated collisions in lock step. Additional information concerning the use of identical spreading codes in an ALOHA CDMA communication system may be found in U.S. Pat. No. 5,537,397 entitled xe2x80x9cSPREAD ALOHA CDMA DATA COMMUNICATIONSxe2x80x9d issued Jul. 16, 1996.
The chip data shown in FIG. 2 is modulated with the data bits which carry the wireless link information such as the transmitted message. FIG. 3 is a timing diagram showing the impression of bit data on the system shown in FIG. 2. In FIG. 3, it is assumed that if a logical xe2x80x9c1xe2x80x9d is being transmitted, the spreading code is transmitting in an un-augmented form. If a logical xe2x80x9c0xe2x80x9d is being transmitted, the inverse of the spreading code is transmitted. The transmission of a logical xe2x80x9c0xe2x80x9d and the inversion of the corresponding chip data is indicated in FIG. 3 by an overbar. In FIG. 3, the remote unit Axe2x80x2 transmits a logical xe2x80x9c1xe2x80x9d followed by a logical xe2x80x9c0xe2x80x9d, the remote unit Cxe2x80x2 transmits a logical xe2x80x9c1xe2x80x9d followed by a logical xe2x80x9c0xe2x80x9d, and the remote unit Exe2x80x2 transmits two consecutive logical xe2x80x9c0xe2x80x9d data bits. In order to examine the effect of the bit data on the inter-channel interference, let us examine the first data bit transmitted by the remote unit Cxe2x80x2 in time slots t5 through t11. Examining the interference from the remote unit Exe2x80x2 to the remote unit Cxe2x80x2 during time periods t5 through t11, we can conclude the interference is equal to 1/n or one seventh of the energy transmitted by the remote unit E during this period due to the DSSS properties described above. A more troublesome case is illustrated by examining the interference from the remote unit Axe2x80x2 to the remote unit Cxe2x80x2 during the same time period. Notice that the data transmitted by the remote unit Axe2x80x2 during the period t5 through t11 transitions from one logical value to another. The transition disrupts the spreading sequence and reduces the orthogonality between the signal from the remote unit Cxe2x80x2 and the signal from the remote unit Axe2x80x2 during that period. For this reason, the interference from the remote unit Axe2x80x2 to the remote unit Cxe2x80x2 during the period t5 to t11 is likely to be greater than 1/n. This phenomena is referred to as partial sequence interference and can significantly reduce the signal to interference ratio experienced by a working system. For example, in a system in which n is equal to 255 operating in a fully loaded ALOHA situation, the resulting signal to interference ratio for each transmission on average is 5.5 decibels (dB) due to the partial sequence interference which results from data transitions rather than 1/255 or approximately 24 dB. The relatively low signal to interference ratio decreases the system performance, thus, increasing the probability of retransmissions due to sources other than collisions. The incidence of retransmission due to these other sources may increase the delay introduced by the system to an intolerably high level.
Therefore, there is a need for a random access system which provides advantageous use of spectral resources as well as tolerable delay.
In a random access, direct sequence spread spectrum (DSSS) system, each time that a remote unit has a message to transmit, it randomly selects one of a set of predetermined sequences with which to modulate the available data. At the occurrence of the next admission boundary, the remote unit transmits the modulated data. If a collision occurs, the remote unit may retransmit the message using another randomly selected one of the predetermined sequences beginning at an admission boundary. By using a second randomly selected sequence, the remote unit need not delay retransmission by an arbitrary amount to avoid lock step collision with another remote unit signal. Thus, by eliminating the need to postpone retransmission attempt randomly, the average delay associated with the random access process is reduced. The use of the recurring admission boundaries allows the remote units to align their bit data boundaries, thus, resulting in a significant decrease in the inter-channel interference.
In a system in which multiple remote units compete for limited communication resources, a remote unit accesses the system by randomly selecting a first sequence from a set of predetermined sequences, and then transmitting a data bit stream modulated with the first sequence beginning at one of a set of recurring admission boundaries If the remote unit determines that the data bit stream has not been successfully received at a hub station, it randomly selects a second sequence from the set of predetermined sequences and transmits the data bit stream modulated with the second sequence beginning at one of the set of recurring admission boundaries. The remote unit may receive a message from the hub station commanding it to remove a reserved sequence from the set of predetermined sequences. In response, the remote unit refrains temporarily from transmitting using the reserved sequence for random access communications.
In one embodiment, the set of predetermined sequences comprises a maximal length sequence and a plurality of rotated versions of the maximal length sequence. In another embodiment, the recurring admission boundaries coincide with boundaries between data bits within the data bit stream. In one embodiment, the remote unit determines whether the data bit stream has been successfully received by monitoring a communication channel which carries the data bit stream modulated with the first sequence to detect a collision with another remote unit signal. In another embodiment, the remote unit determines that the data bit stream has not been successfully received by determining whether an acknowledgment of receipt of the data bit stream is received from the hub station.
In one embodiment, the remote unit randomly selects a frequency channel over which to transmit the data bit stream modulated with the second sequence. In yet another embodiment, the remote unit randomly delays transmitting the data bit stream modulated with the second sequence.
The set of predetermined sequences may be Walsh codes or Walsh codes which have been masked with a second code. The second code may determine spectral properties of the set of predetermined sequences. The set of predetermined sequences may comprise a maximal length sequence and a plurality of rotated versions of the maximal length sequence. The data bit stream modulated with the first sequence may be transmitted using a higher order modulation scheme. For example, the higher order modulation scheme may be a quadrature amplitude modulation comprising at least 16 values, or 8 or 16-ary phase shift keying.
The remote unit may receive a power control command from a hub station in order to set a power level used to transmit to within about 1 dB of accuracy. The transmission path may comprise a satellite link. The remote unit may receive a command from the hub station to use a reserved one of the set of predetermined sequences. In such a case, the remote unit transmits a data bit stream modulated with the reserved one of the set of predetermined sequences beginning at one of the set of recurring admission boundaries.
The hub station correlates one or more of the set of predetermined sequences with a set of incoming data samples beginning at one of a set of recurring admission boundaries If the hub station detects a signal level above a detection threshold corresponding to a detected one of the set of predetermined sequences, it demodulates a remote unit signal using the detected one of the set of predetermined sequences In one aspect, hub station detects a remote unit message length which exceeds a threshold. The hub station sends a message to other remote units temporarily removing the detected one from the set of predetermined sequences such that the other remote units refrain from using the detected one of the set of predetermined sequences for random access communications. The hub station may transmit an indication of the set of recurring admission boundaries to a set of remote units. In one embodiment, the hub station demodulates a series of non-contention channels which share a common frequency spectrum with the set of incoming signal samples which may consume 10% to 25% of the capacity of the common frequency spectrum and are bit aligned with the set of recurring admission boundaries. The hub station may send a power control command to the remote unit in order to set a power level at which the remote unit is transmitting to within about 1 dB of accuracy.
The hub station may monitor a plurality of random access, direct sequence spread spectrum communication channels for random access communication signals. The hub station may temporarily allocate a chosen one of the plurality of random access, direct sequence spread spectrum communication channels to a particular remote unit. The hub station may command other remote units using the plurality of random access, direct sequence spread spectrum communication channels to abstain temporarily from using the chosen one for random access communication.
A remote unit may be comprised of a process which randomly selects a first sequence from a set of predetermined sequences, a process which transmits a data bit stream modulated with the first sequence beginning at one of a set of recurring admission boundaries, a process which determines that the data bit stream has not been successfully received at a hub station, a process which randomly selects a second sequence from the set of predetermined sequences, and a process which transmits the data bit stream modulated with the second sequence beginning at one of the set of recurring admission boundaries. The remote unit may further comprise a process which randomly selects a frequency channel over which to transmit the data bit stream modulated with the first and second sequence. The remote unit may comprise a process which randomly delays transmitting the data bit stream modulated with the second sequence. In addition, the remote unit may comprise a process which receives a command from the hub station to use a reserved one of the set of predetermined sequences, and a process which transmits a data bit stream modulated with the reserved one of the set of predetermined codes beginning at one of the set of recurring admission boundaries.